#include "QuickSort.h"

double QuickSort::ordenar()
{
    if (vetor == NULL) return(-1);
    tempo_iniciar();
    quicksort(0,tamanho_vetor-1);
    return(tempo_terminar());
}

size_t QuickSort::particao(size_t esq, size_t dir)
{
    if (esq >= dir) return(esq);
    size_t i = esq;
    for (size_t j=(esq+1) ; j<=dir ; j++)
        if (funcao_comparacao(get(j),get(esq)) < 0)
        {
            i++;
            trocar(i,j);
        }
    trocar(esq,i);
    //cout<<"*** particao("<<esq<<","<<dir<<"): "<<i<<" ***"<<endl;
    return(i);
}

void QuickSort::quicksort(size_t esq, size_t dir)
{
    if (esq < dir)
    {
        //cout<<"\n$$$ quicksort("<<esq<<","<<dir<<") $$$"<<endl;
        size_t p = particao(esq,dir);
        if (p != 0) quicksort(esq,p-1);
        quicksort(p+1,dir);
    }
}
